Problem statement: zenit11ckh

h) (30 bodov)

Pre veľký úspech má pre teba personálne oddelenie ešte jednu úlohu. Toto oddelenie má veľký zoznam zamestnancov, ktorých ma zoradených podľa neznámeho kľúča. O každom zamestnancovi má zaznamenané jedno nezáporné celé číslo – spokojnosť nadriadeného s prácou daného zamestnanca. Raz za čas samozrejme príde aktualizácia tejto spokojnosti. Okrem toho raz za čas príde z vyššieho vedenia direktíva typu: “vyberte jedného zamestnanca, s ktorým je spokojnosť aspoň Z a odmeňťe ho za mimoriadny prínos pre inštitúciu”. Nadriadeným nezáleží na tom, ktorý zamestnanec to bude a preto pracuje personálne oddelenie tak, že ide po zozname zamestnancov od začiatku a odmení prvého vyhovujúceho zamestnanca s danou spokojnosťou. Napíšte program, ktorý pomôže personálnemu oddeleniu. Na vstupe sú na prvom riadku dve hodnoty: počet zamestnancov N a počet dotazov M (1 <= N,M <= 100,000). Nasleduje M riadkov, ktoré môžu byť dvoch tvarov:

• 1 X Y, spokojnosť so zamestnancom s poradovým číslom X sa mení na Y.

• 2 Z, odmeňte nejakého zamestnanca, s ktorým vládne spokojnosť aspoň Z.

V uvedených dotazoch je X medzi 1 a N. Y a Z sú celé nezáporné čísla nepresahujúce miliardu. Na začiatku je spokojnosť so všetkými rovná nule. Pre každú požiadavku typu 2 vypíšte na samostatný riadok najmenšie číslo zamestnanca, s ktorým v danom momente vládne spokojnosť aspoň Z. Ak taký zamestnanec neexistuje, vypíšte nikto. Za priamočiare riešenie bude približne polovica bodov.

Príklad:

Vstup:

5 5
2 2
1 3 3
2 2
1 2 5
2 2

Výstup:

nikto
3
2

Vstup:

5 7
1 3 7
1 4 10
2 8
2 6
1 3 4
2 6
2 3

Výstup:

4
3
4
3

Posledný príklad je veľký a preto ho tu nebudeme uvádzať.